package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;

import java.util.LinkedList;

/**
 * 接雨水
 * see LC84
 * <p>
 * 股票买卖122用了一种 currentMin的写法, 这题好像不那么简单
 *
 * @author tzp
 * @since 2020/9/24
 */
public class LC42 implements StackProblem {
    public int trap(int[] heights) {
        int sum = 0;
        if (heights.length <= 2) return sum;
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < heights.length; i++) {
            while (stack.size() > 0 && heights[i] > heights[stack.peekLast()]) {
                Integer lastI = stack.pollLast();
                int lastV = heights[lastI];
                if (stack.size() > 0) {
                    Integer lastlastI = stack.peekLast();
                    Integer lastlastV = heights[lastlastI];
                    sum += (i - lastlastI - 1) /*宽*/
                            * (Math.min(lastlastV, heights[i]) - lastV) /*高*/;
                }
            }
            stack.addLast(i);
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new LC42().trap(new int[]{1, 2, 1, 3, 2, 1, 2, 4, 3, 2, 3, 2}));//6
        System.out.println(new LC42().trap(new int[]{4, 2, 3}));//1
        System.out.println(new LC42().trap(new int[]{4, 2, 0, 3, 2, 5}));//9
    }
}
